/* Author: DO HOANG HAI
 * Main.java
 *
 * Created on June 6, 2006, 1:38 PM
 *
 * Description: This project demonstrate how to use ShortestPath searching algorithm to find the shortest path in a graph
 */

package shortestpath;
import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
/**
 *
 * @author hai
 */
public class Main {
    
    private static int[][] dis=new int[15][15];
    private static int numOfNode;
    /** Creates a new instance of Main */
    public Main() {
    }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        readData();
        Scanner input=new Scanner(System.in);
        System.out.println("Find the shortest path from Node id: ");
        int startNodeId=input.nextInt();
        System.out.println("The destination node id: ");
        int desID=input.nextInt();
        buildShortestPathTree(startNodeId,desID);
                
    }
    
    public static void buildShortestPathTree(int desId, int rootId){
        
        Node[] ar=new Node[20];
        for (int i=0; i<numOfNode; i++)
            ar[i]=new Node(i);
        
        for (int i=0; i<numOfNode; i++)
            ar[i].setCost(100);   // 100 is considered as infinite
          //  else {
            //    ar[i].setCost(dis[rootId][i]);
             //   ar[i].parent=ar[rootId];
            //}
        ar[rootId].setCost(0);
        
        Heap PQueue=new Heap();
        for (int i=0; i<numOfNode; i++)
            PQueue.insert(ar[i]);
        
        int[] stillInTheHeap= new int[20];
        for (int i=0; i<numOfNode; i++)
            stillInTheHeap[i]=1;   
        
        while(!PQueue.isEmpty()){
            Node temp=PQueue.deleteLeast();
            stillInTheHeap[temp.id]=0;
            for (int i=0; i<numOfNode; i++)
                if(stillInTheHeap[i]==1 && dis[temp.id][i]!=0)
                    if(ar[i].getCost()>temp.getCost()+dis[temp.id][i]){
                        try{
                            ar[i].parent=temp;
                            ar[i].changeCost(temp.getCost()+dis[temp.id][i]);
                                                        
                        }
                        catch(NodeValueChangeException e){
                            PQueue.restructure(e.id);
                        }
                
                    }            
        }
        System.out.println("Shortest path from node "+desId+" to node "+rootId+" is: ");
        Node cur=ar[desId];
        int length = 0;
        while(cur.id!=rootId){
            System.out.print(" "+cur.id);
            Node tempNode = cur;
            cur=cur.parent;
            
            length = length + dis[tempNode.id][cur.id];
        }
        System.out.println("  "+rootId);
        System.out.println("The distance is: " + length);
    }
        
        
    
    public static void readData(){
        try{
            Scanner reader=new Scanner(new File("src/testData.txt"));
            int i=0;
           
            while(reader.hasNextLine()){
                int j=0;
                String aLine=reader.nextLine();
                Scanner extractLine=new Scanner(aLine);
                while(extractLine.hasNext()){
                    dis[i][j]=extractLine.nextInt();
                    j++;
                }                
                i++;
            }
            numOfNode=i;
            for (int m=0; m<numOfNode; m++){
                for (int n=0; n<numOfNode; n++)
                    System.out.print("  "+dis[m][n]);
                System.out.println();
            }
            reader.close();
            
        }
        catch(FileNotFoundException e){
            System.out.println("File is not found");
        }
        
    }   
}
